# 两数相加： https://leetcode-cn.com/problems/add-two-numbers/


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 以前写的， 看注释挺详细的，直接复制过来了~~
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """ 
            对于链表的问题，一定要习惯性的设立头结点！ 虽然这道题设立头结点只是方便对结果链表增加元素
            1. 头结点可以使首元结点像其他节点一样去处理，不需要特殊处理 
            2. 头结点可以保证 空链表判断的一致性。 都是L.next == None
        """
        node1, node2 = ListNode(), ListNode()
        # 设立头结点
        node1.next = l1; node2.next = l2
        # 当前元素指针，默认指向头结点
        cur1 = node1; cur2 = node2
        # 目标链表存储结果
        head = ListNode()
        p = head
        # 进位
        carry = 0
        # 当任意链表下一节点不为 None
        while cur1.next or cur2.next:
            dig1 = cur1.next.val if cur1.next else 0
            dig2 = cur2.next.val if cur2.next else 0
            # 更新指针
            if cur1.next: cur1 = cur1.next 
            if cur2.next: cur2 = cur2.next 

            # 计算和， 计算进位
            sum = dig1 + dig2 + carry
            carry = sum // 10
            # 加入结果链表
            p.next = ListNode(sum % 10)
            p = p.next

        # 如果进位不为0，那么还要加上进位
        if carry != 0: p.next = ListNode(carry)

        # 不返回头结点
        return head.next


# 这是刚写的： 未加首元结点的方式（上面是以前写的，概念略不清晰）
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """ 
        """
        newHead = ListNode(0)
        newP = newHead
        p1, p2 = l1, l2
        jin = 0
        while p1 or p2:
            # 1. 找到操作数 a, b , 进位 jin， 并计算当前计算的进位
            a = p1.val if p1 else 0
            b = p2.val if p2 else 0
            div = (a + b + jin) % 10
            jin = (a + b + jin) // 10
            # 2. 更新指针后移, 要注意 p1, p2 为 None的判断，不可前移
            if p1: p1 = p1.next 
            if p2: p2 = p2.next
            # 3. 赋值
            newP.val = div
            # 4. 判断是否需要创建新节点
            if p1 or p2:
                newP.next = ListNode(0)
                newP = newP.next

        # 如果最后还有进位， 那就 再创建一个节点
        if jin > 0:
            newP.next = ListNode(jin)
        
        return newHead


# 还可以优化其中的判断， 1. 判断最后是否还有 jin， 2。 是否创建下一个节点
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """ 
            把 jin 直接赋值到 节点中去，简省了步骤
        """
        newHead = ListNode(0)
        newP = newHead
        p1, p2 = l1, l2
        while p1 or p2:
            # 1. 找到操作数 a, b , 进位 jin， 并计算当前计算的进位
            a = p1.val if p1 else 0
            b = p2.val if p2 else 0
            div = (a + b + newP.val) % 10
            jin = (a + b + newP.val) // 10
            # 2. 更新指针后移, 要注意 p1, p2 为 None的判断，不可前移
            if p1: p1 = p1.next 
            if p2: p2 = p2.next
            # 3. 赋值
            newP.val = div
            # 4. 判断是否需要创建新节点
            if p1 or p2 or jin > 0:
                newP.next = ListNode(jin)
                newP = newP.next
        
        return newHead
